|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 複 ： [ふく] 1. (n,pref) double 2. compound ・ 複雑 ： [ふくざつ] 1. (adj-na,n) complexity 2. complication ・ 雑 ： [ざつ] 1. (adj-na,n) rough 2. crude ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP（あるいは両方）と考えられている（P≠NP予想）。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 ''L'' が UP に属するのは、2入力の多項式時間アルゴリズム ''A'' と定数 c があって、次が成り立つ場合である（アルゴリズム A は ''L'' を多項式時間で検証する）。 :L = 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「UP (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|